/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
/* 
为了生成范围 [1, n] 中所有可能的 k 个数的组合，可以使用回溯法。
回溯法通过递归遍历所有可能的数字选择，逐步构建组合，直到组合长度达到 k。

方法思路
递归回溯：从第一个数字开始，递归选择当前数字或跳过，继续处理后续数字。
剪枝优化：如果剩余数字不足以构成 k 个数的组合，直接终止递归，减少不必要的计算。
边界条件：当组合长度达到 k 时，将当前组合加入结果集。
*/
var combine = function (n, k) {
  const result = [];

  // 回溯函数：start表示当前可选的起始数字，path表示当前组合
  const backtrack = (start, path) => {
    // 如果当前组合长度等于k，加入结果集
    if (path.length === k) {
      result.push([...path]);
      return;
    }

    // 计算剩余数字数量，若不足则剪枝
    const remaining = n - start + 1;
    if (remaining < k - path.length) {
      return;
    }

    // 选择当前数字
    for (let i = start; i <= n; i++) {
      path.push(i);
      backtrack(i + 1, path);
      path.pop(); // 回溯，撤销选择
    }
  };

  // 从1开始回溯
  backtrack(1, []);

  return result;
};